9.6 Set Operations using Vectors

Calc includes several commands which interpret vectors as sets of objects. A set is a collection of objects; any given object can appear only once in the set. Calc stores sets as vectors of objects in sorted order. Objects in a Calc set can be any of the usual things, such as numbers, variables, or formulas. Two set elements are considered equal if they are identical, except that numerically equal numbers like the integer 4 and the float 4.0 are considered equal even though they are not “identical.” Variables are treated like plain symbols without attached values by the set operations; subtracting the set ‘[b]’ from ‘[a, b]’ always yields the set ‘[a]’ even though if the variables ‘a’ and ‘b’ both equaled 17, you might expect the answer ‘[]’.

If a set contains interval forms, then it is assumed to be a set of real numbers. In this case, all set operations require the elements of the set to be only things that are allowed in intervals: Real numbers, plus and minus infinity, HMS forms, and date forms. If there are variables or other non-real objects present in a real set, all set operations on it will be left in unevaluated form.

If the input to a set operation is a plain number or interval form a, it is treated like the one-element vector ‘[a]’. The result is always a vector, except that if the set consists of a single interval, the interval itself is returned instead.

See Logical Operations, for the in function which tests if a certain value is a member of a given set. To test if the set ‘A’ is a subset of the set ‘B’, use ‘vdiff(A, B) = []’.

The V + (calc-remove-duplicates) [rdup] command converts an arbitrary vector into set notation. It works by sorting the vector as if by V S, then removing duplicates. (For example, [a, 5, 4, a, 4.0] is sorted to ‘[4, 4.0, 5, a, a]’ and then reduced to ‘[4, 5, a]’). Overlapping intervals are merged as necessary. You rarely need to use V + explicitly, since all the other set-based commands apply V + to their inputs before using them.

The V V (calc-set-union) [vunion] command computes the union of two sets. An object is in the union of two sets if and only if it is in either (or both) of the input sets. (You could accomplish the same thing by concatenating the sets with |, then using V +.)

The V ^ (calc-set-intersect) [vint] command computes the intersection of two sets. An object is in the intersection if and only if it is in both of the input sets. Thus if the input sets are disjoint, i.e., if they share no common elements, the result will be the empty vector ‘[]’. Note that the characters V and ^ were chosen to be close to the conventional mathematical notation for set union and intersection.

The V - (calc-set-difference) [vdiff] command computes the difference between two sets. An object is in the difference ‘A - B’ if and only if it is in ‘A’ but not in ‘B’. Thus subtracting ‘[y,z]’ from a set will remove the elements ‘y’ and ‘z’ if they are present. You can also think of this as a general set complement operator; if ‘A’ is the set of all possible values, then ‘A - B’ is the “complement” of ‘B’. Obviously this is only practical if the set of all possible values in your problem is small enough to list in a Calc vector (or simple enough to express in a few intervals).

The V X (calc-set-xor) [vxor] command computes the “exclusive-or,” or “symmetric difference” of two sets. An object is in the symmetric difference of two sets if and only if it is in one, but not both, of the sets. Objects that occur in both sets “cancel out.”

The V ~ (calc-set-complement) [vcompl] command computes the complement of a set with respect to the real numbers. Thus ‘vcompl(x)’ is equivalent to ‘vdiff([-inf .. inf], x)’. For example, ‘vcompl([2, (3 .. 4]])’ evaluates to ‘[[-inf .. 2), (2 .. 3], (4 .. inf]]’.

The V F (calc-set-floor) [vfloor] command reinterprets a set as a set of integers. Any non-integer values, and intervals that do not enclose any integers, are removed. Open intervals are converted to equivalent closed intervals. Successive integers are converted into intervals of integers. For example, the complement of the set ‘[2, 6, 7, 8]’ is messy, but if you wanted the complement with respect to the set of integers you could type V ~ V F to get ‘[[-inf .. 1], [3 .. 5], [9 .. inf]]’.

The V E (calc-set-enumerate) [venum] command converts a set of integers into an explicit vector. Intervals in the set are expanded out to lists of all integers encompassed by the intervals. This only works for finite sets (i.e., sets which do not involve ‘-inf’ or ‘inf’).

The V : (calc-set-span) [vspan] command converts any set of reals into an interval form that encompasses all its elements. The lower limit will be the smallest element in the set; the upper limit will be the largest element. For an empty set, ‘vspan([])’ returns the empty interval ‘[0 .. 0)’ .

The V # (calc-set-cardinality) [vcard] command counts the number of integers in a set. The result is the length of the vector that would be produced by V E, although the computation is much more efficient than actually producing that vector.

Another representation for sets that may be more appropriate in some cases is binary numbers. If you are dealing with sets of integers in the range 0 to 49, you can use a 50-bit binary number where a particular bit is 1 if the corresponding element is in the set. See Binary Functions, for a list of commands that operate on binary numbers. Note that many of the above set operations have direct equivalents in binary arithmetic: b o (calc-or), b a (calc-and), b d (calc-diff), b x (calc-xor), and b n (calc-not), respectively. You can use whatever representation for sets is most convenient to you.

The b u (calc-unpack-bits) [vunpack] command converts an integer that represents a set in binary into a set in vector/interval notation. For example, ‘vunpack(67)’ returns ‘[[0 .. 1], 6]’. If the input is negative, the set it represents is semi-infinite: ‘vunpack(-4) = [2 .. inf)’. Use V E afterwards to expand intervals to individual values if you wish. Note that this command uses the b (binary) prefix key.

The b p (calc-pack-bits) [vpack] command converts the other way, from a vector or interval representing a set of nonnegative integers into a binary integer describing the same set. The set may include positive infinity, but must not include any negative numbers. The input is interpreted as a set of integers in the sense of V F (vfloor). Beware that a simple input like ‘[100]’ can result in a huge integer representation (‘2^100’, a 31-digit integer, in this case).